Course syllabus
Simulering
Simulation
ETS061, 7,5 credits, A (Second Cycle)
Valid for: 2016/17
Decided by: Education Board A
Date of Decision: 2016-04-05
General Information
Elective for: C4-ks, D4-ks, E4-ks, I4, I4-pvs, Pi4
Language of instruction: The course will be given in English on demand
Aim
The purpose of the course is to give an introduction to discrete
event simulation, basic optimization approaches, and heuristic
methods such as simulated annealing, tabu search, evolutionary
algorithms and GRASP.
Learning outcomes
Knowledge and understanding
For a passing grade the student must
- Have some knowledge on different kinds of dynamic models that
are used in engineering
- Describe the event-scheduling and the process-oriented approach
to writing simulation programs
- Know how to estimate the accuracy of simulation results
- Know the basic notions in optimization theory
- Know how to solve linear and integer optimization problems
- Know basic concepts of the computational complexity theory
- Know the most common heuristic methods for optimization
Competences and skills
For a passing grade the student must
- Write well-structured simulation programs in a general
programming language
- Estimate the accuracy of simulation results
- Be able to verify and validate simulation programs
- Know what is a general static optimization problem, a general
convex problem and its dual, and a combinatorial optimization
problem
- Understand how duality applies to linear programming (LP)
problems and column generation in LP
- Be able to apply the simplex algorithm to linear programming
problems
- Apply LP approximation to nonlinear objective functions
- Understand the connection between integer programming (IP) and
LP
- Be able to apply the branch-and-bound method to IP, and
understand what is the cutting plane method in IP
- Understand the basic notions in computational complexity,
including polynomial problems and NP-hardness
- Have a basic knowledge of heuristic methods in combinatorial
optimization
- Be able to implement simulated annealing and evolutionary
algorithms
- Be familiar with Monte Carlo techniques
Judgement and approach
For a passing grade the student must
- Show knowledge of the possibilities and limitations of
simulation experiments
- Be able to independently construct models for optimization
problems and to apply the GUROBI optimization package (or alike)
for resolving them with full understanding of the solution process
and output data
- Be able to choose and apply a heuristic method to solve an
optimization problems
Contents
In the course we start by studying discrete event simulation.
Students learn to write process-oriented and event-scheduling
simulation programs in general programming languages. Estimation of
accuracy, random number generation, methods for studying rare
events, verification and validation are also covered.
Then we proceed to optimization techniques. We study convex
problems and their duals. Further, we go to linear programs (LP),
the simplex algorithm, and the column generation technique. We show
how to model non-linearity. After that we consider integer
programming (IP), its relation to LP, and the branch-and-bound
method for IP. We also mention the cutting plane method for IP and
sketch the computational complexity theory, including the notions
of polynomial problems and NP-hardness.
Finally, we consider heuristic methods for combinatorial
optimization problems viewed as optimization through simulation. We
explain the local search and the role of randomness. We explain the
basic meta-heuristics such as simulated annealing, evolutionary
algorithms, and GRASP. We also illustrate the Monte Carlo
techniques.
Examination details
Grading scale: TH
Assessment: Approved home assignments, which are graded, gives grade 3. An approved take-home examination is required for grades 4 and 5.
Admission
Required prior knowledge: Programming, Basic probability, Statistical methods, Mathematical analysis.
The number of participants is limited to: No
The course overlaps following course/s: ETS060, ETS120
Reading list
- Nyberg, C, Compendium in simulation.
- Michal Pioro: Network Optimization Techniques, Chapter 18 in E. Serpedin, E., Chen, T., and Rajan, D. (eds.): Signal Processing, Communications, and Networking,. CRC Press, 2012, ISBN: 978-1-4398-5513-3.
Contact and other information
Course coordinator: Christian Nyberg, Christian.Nyberg@eit.lth.se
Course homepage: http://www.eit.lth.se/course/ets061